/*
2021-10-17
https://www.acwing.com/problem/content/4002/
*/ 
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;
ll a,m;

ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}

ll phi(ll x)
{
    ll res=x;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0) 
        {
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) res=res/x*(x-1);
    return res;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a>>m;
        ll d=gcd(a,m);
        cout<<phi(m/d)<<endl;
    }
    return 0;
}
